package LeetCode;

public class LeetCodeMain25 {
    public int canCompleteCircuit1(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length; i++) {
            int tmp = gas[i] - cost[i];
            int index = (i + 1) % gas.length;
            while (index != i && tmp > 0) {
                tmp+=gas[index] - cost[index];
                index = (index + 1) % gas.length;
            }
            if (tmp>=0&&index==i){
                return i;
            }
        }
        return -1;
    }
    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int sum=0;
        int min=Integer.MAX_VALUE;
        for (int i = 0; i < gas.length; i++) {
            sum+=gas[i]-cost[i];
            if (sum<min){
                min=sum;
            }
        }
        if(min>=0){
            return 0;
        }
        if (sum<0){
            return -1;
        }
        for (int i = gas.length-1; i >=0 ; i--) {
            min+=gas[i]-cost[i];
            if (min>=0){
                return i;
            }
        }
        return -1;
    }
    public int canCompleteCircuit3(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            curSum+=gas[i]-cost[i];
            totalSum+=gas[i]-cost[i];
            if (curSum<0){
                curSum=0;
                start=i+1;
            }
        }
        if (totalSum>=0){
            return start;
        }
        return -1;
    }

}
